package leetcode.code0894;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	public List<TreeNode> allPossibleFBT(int n) {
		Map<Integer, List<TreeNode>> map = new HashMap<>();
		List<TreeNode> ans = new ArrayList<>();
		ans.add(new TreeNode(0));
		map.put(1, ans);
		return this.find(n, map);
	}

	public List<TreeNode> find(int n, Map<Integer, List<TreeNode>> map) {
		if (map.containsKey(n)) {
			return map.get(n);
		}
		List<TreeNode> ans = new ArrayList<>();
		int l = 1, r = n - l - 1;
		while (r > 0) {
			List<TreeNode> lefts = this.find(l, map);
			List<TreeNode> rights = this.find(r, map);
			for (TreeNode left : lefts) {
				for (TreeNode right : rights) {
					TreeNode cur = new TreeNode(0);
					cur.left = left;
					cur.right = right;
					ans.add(cur);
				}
			}
			l += 2;
			r -= 2;
		}
		map.put(n, ans);
		return ans;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.allPossibleFBT(5);

	}

}
